#pragma once

template <typename T> class SLLIter;

template <typename T>
class SLList
{
	friend class SLLIter<T>;

	typedef struct _node
	{
		T data;
		_node * next;

		_node(T val = 0)
		{
			data = val;
			next = 0;
		}
	} Node;

	Node * head;

	unsigned int numNodes;

public:
	///////////////////////////////////////////////////////////////////////////////
	// Function : Constructor
	// Notes : constructs an empty list
	///////////////////////////////////////////////////////////////////////////////
	SLList();

	///////////////////////////////////////////////////////////////////////////////
	// Function : Destructor
	// Notes : Destroys the list
	///////////////////////////////////////////////////////////////////////////////
	~SLList();

	///////////////////////////////////////////////////////////////////////////////
	// Function : Assignment Operator
	///////////////////////////////////////////////////////////////////////////////
	SLList<T>& operator=(const SLList<T>& that);

	///////////////////////////////////////////////////////////////////////////////
	// Function : Copy Constructor
	///////////////////////////////////////////////////////////////////////////////
	SLList(const SLList<T>& that);

	///////////////////////////////////////////////////////////////////////////////
	// Function : addHead
	// Parameters :	v - the item to add to the list
	///////////////////////////////////////////////////////////////////////////////
	void addHead(const T& v);

	///////////////////////////////////////////////////////////////////////////////
	// Function : clear
	// Notes : clears the list, freeing any dynamic memory
	///////////////////////////////////////////////////////////////////////////////
	void clear();

	///////////////////////////////////////////////////////////////////////////////
	// Function : insert
	// Parameters :	index - an iterator to the location to insert at
	//				v - the item to insert
	// Notes : do nothing on a bad iterator
	///////////////////////////////////////////////////////////////////////////////
	void insert(SLLIter<T>& index, const T& v);
	void insertAt(const unsigned int index, const T& val);

	///////////////////////////////////////////////////////////////////////////////
	// Function : remove
	// Parameters :	index - an iterator to the location to remove from
	// Notes : do nothing on a bad iterator
	///////////////////////////////////////////////////////////////////////////////
	void remove(SLLIter<T>& index);
	void removeAt(const unsigned int index);

	inline unsigned int size() const;

	T& operator[](unsigned int index);

};

template <typename T>
SLList<T>::SLList() : head(0), numNodes(0)
{

}

template <typename T>
T& SLList<T>::operator[](unsigned int index)
{
	SLLIter<T> itt(*this);
	for(unsigned int i = 0; i < index; i++)		++itt;
	
	return itt.current();
}
///////////////////////////////////////////////////////////////////////////////
// Function : Destructor
// Notes : Destroys the list
///////////////////////////////////////////////////////////////////////////////
template <typename T>
SLList<T>::~SLList()
{
	while(head != NULL)
	{
		Node * temp = head;
		head = head->next;
		delete temp;
	}
}

///////////////////////////////////////////////////////////////////////////////
// Function : Assignment Operator
///////////////////////////////////////////////////////////////////////////////
template <typename T>
SLList<T>& SLList<T>::operator=(const SLList<T>& that)
{

	if(this != &that)
	{
		clear();
		Node * temp = that.head;
		Node * temp1 = head;

		while(temp != NULL)
		{
			Node * newNode = new Node(temp->data);

			if(head == NULL)
			{
				head = newNode;
				temp1 = head;
			}
			else
			{
				temp1->next = newNode;
				temp1 = temp1->next;
			}

			temp = temp->next;
		}
	}

	return *this;
}

///////////////////////////////////////////////////////////////////////////////
// Function : Copy Constructor
///////////////////////////////////////////////////////////////////////////////
template <typename T>
SLList<T>::SLList(const SLList<T>& that) : head(0)
{

	clear();

	Node * temp = that.head;
	Node * temp1 = head;
	while(temp != NULL)
	{
		Node * newNode = new Node(temp->data);

		if(head == NULL)
		{
			head = newNode;
			temp1 = head;
		}

		else
		{
			temp1->next = newNode;
			temp1 = temp1->next;
		}

		temp = temp->next;
	}

}

///////////////////////////////////////////////////////////////////////////////
// Function : addHead
// Parameters :	v - the item to add to the list
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void SLList<T>::addHead(const T& v)
{
	Node * newNode = new Node(v);
	if(newNode != NULL)
	{
		newNode->next = head;
		head = newNode;
		numNodes++;
	}
	else
	{
		//Later throw an exception
	}

}

///////////////////////////////////////////////////////////////////////////////
// Function : clear
// Notes : clears the list, freeing any dynamic memory
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void SLList<T>::clear()
{
	Node * temp;
	while(head != NULL)
	{
		temp = head;
		head = head->next;
		delete temp;
	}

	numNodes = 0;
}

///////////////////////////////////////////////////////////////////////////////
// Function : insert
// Parameters :	index - an iterator to the location to insert at
//				v - the item to insert
// Notes : do nothing on a bad iterator
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void SLList<T>::insert(SLLIter<T>& index, const T& v)
{
	if(index.cur == NULL)
		return;

	Node * newNode = new Node(v);

	if(newNode != NULL)
	{
		if(head == index.cur)
		{
			newNode->next = head;
			index.cur = newNode;
			head = newNode;
		}
		else
		{
			newNode->next = index.cur;
			index.prev->next = newNode;
		}

		index.cur = newNode;
		numNodes++;
	}
	else
	{
		//Later throw an exceptions
	}
}

///////////////////////////////////////////////////////////////////////////////
// Function : remove
// Parameters :	index - an iterator to the location to remove from
// Notes : do nothing on a bad iterator
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void SLList<T>::remove(SLLIter<T>& index)
{
	if(index.cur == head)
	{
		if (index.cur != NULL)
		{

			Node * temp = index.cur;
			index.cur = index.cur->next;

			head = index.cur;
			delete temp;
			numNodes--;
		}
	}
	else
	{
		if(index.cur != NULL)
		{
			index.prev->next = index.cur->next;

			delete index.cur;
			index.cur = index.prev->next;
			numNodes--;
		}
	}


}

template <typename T>
unsigned int SLList<T>::size() const
{
	return numNodes;
}

template <typename T>
void SLList<T>::insertAt(const unsigned int index, const T & val)
{
	SLLIter<T> itt(*this);
	for(unsigned int i = 0; i < index; i++)		++itt;

	Node * temp = new Node(val);
	
	itt.prev->next = temp;
	temp->next = itt.cur;
	itt.cur = temp;

	numNodes++;

}

template <typename T>
void SLList<T>::removeAt(const unsigned int index)
{

	SLLIter<T> itt(*this);
	for(unsigned int i = 0; i < index; i++)		++itt;


	Node * temp = itt.cur;

	itt.prev->next = itt.cur->next;
	delete temp;

	numNodes--;
}




template <typename T>
class SLLIter	
{
	friend class SLList<T>;

	typename SLList<T>::Node * cur;
	typename SLList<T>::Node * prev;
	SLList<T> * list;
public:
	///////////////////////////////////////////////////////////////////////////////
	// Function : Constructor
	// Parameters :	listToIterate - the list to iterate
	///////////////////////////////////////////////////////////////////////////////
	SLLIter(SLList<T>& listToIterate);
	SLLIter(const SLList<T>& listToIterate);

	///////////////////////////////////////////////////////////////////////////////
	// Function : begin
	// Notes : moves the iterator to the head of the list
	///////////////////////////////////////////////////////////////////////////////
	void begin();

	///////////////////////////////////////////////////////////////////////////////
	// Function : end
	// Notes : returns true if we are at the end of the list, false otherwise
	///////////////////////////////////////////////////////////////////////////////
	bool end() const;

	///////////////////////////////////////////////////////////////////////////////
	// Function : operator++
	// Notes : move the iterator forward one node
	///////////////////////////////////////////////////////////////////////////////
	SLLIter<T>& operator++();

	///////////////////////////////////////////////////////////////////////////////
	// Function : current
	// Notes : returns the item at the current iterator location
	///////////////////////////////////////////////////////////////////////////////
	T& current() const;

};

///////////////////////////////////////////////////////////////////////////////
// Function : Constructor
// Parameters :	listToIterate - the list to iterate
///////////////////////////////////////////////////////////////////////////////
template <typename T>
SLLIter<T>::SLLIter(SLList<T>& listToIterate) : prev(0), cur(listToIterate.head), list(&listToIterate)
{

}


template <typename T>
SLLIter<T>::SLLIter(const SLList<T>& listToIterate) : prev(0), cur(listToIterate.head), list(&listToIterate)
{

}

///////////////////////////////////////////////////////////////////////////////
// Function : begin
// Notes : moves the iterator to the head of the list
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void SLLIter<T>::begin()
{
	prev = NULL;
	cur = this->list->head;
}

///////////////////////////////////////////////////////////////////////////////
// Function : end
// Notes : returns true if we are at the end of the list, false otherwise
///////////////////////////////////////////////////////////////////////////////
template <typename T>
bool SLLIter<T>::end() const
{
	return (cur == NULL);
}

///////////////////////////////////////////////////////////////////////////////
// Function : operator++
// Notes : move the iterator forward one node
///////////////////////////////////////////////////////////////////////////////
template <typename T>
SLLIter<T>& SLLIter<T>::operator++()
{
	if(cur != NULL)
	{
		prev = cur;
		cur = cur->next;
	}

	return *this;
}

///////////////////////////////////////////////////////////////////////////////
// Function : current
// Notes : returns the item at the current iterator location
///////////////////////////////////////////////////////////////////////////////
template <typename T>
T& SLLIter<T>::current() const
{

	//if(cur != NULL)
	return cur->data;


	//return *(new T());
}